package recursion;

import datastructure.linkedlist.Node;

/**
 * Add two linked list and 
 * return a single linked list
 * 
 * Input : (3 -> 1 -> 5) + (5 ->9 ->2)
 * Output : 8 -> 0 -> 8
 * 
 * @author Lei
 */
public class AddTwoLinkedList {

    // assume two link list's lenghs are same
    public static Node addTwoLinkedList(Node Node1, Node Node2, int jinwei) {
        Node newNode = new Node();
        int newValue = Node1.value + Node2.value + jinwei;
        int newJinwei = 0;
        if (newValue >= 10) {
            newNode.value = newValue - 10;
            newJinwei = 1;
        }
        else {
            newNode.value = newValue;
        }

        if (Node1.next != null && Node2.next != null) {
            newNode.next = addTwoLinkedList(Node1.next, Node2.next, newJinwei);
        }

        return newNode;

    }

    public static void main(String[] args) {

        Node n1 = new Node(3);
        Node n2 = new Node(1);
        Node n3 = new Node(5);

        Node n4 = new Node(5);
        Node n5 = new Node(9);
        Node n6 = new Node(2);

        n1.next = n2;
        n2.next = n3;

        n4.next = n5;
        n5.next = n6;

        Node p = AddTwoLinkedList.addTwoLinkedList(n1, n4, 0);
        while (p != null) {
            System.out.println(p.value);
            p = p.next;
        }

    }
}
